1. Field of the Invention
The present invention generally relates to scheduling of computational loads in a multiprocessor computer system, and more particularly to a method of assigning computational loads associated with multiple regions having placeable objects for the physical design of an integrated circuit.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and requires connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements combined to perform a logic function. Cell types include, for example, core cells, scan cells, input/output (I/O) cells, and memory (storage) cells.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins including information about the various components such as transistors, resistors and capacitors. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The process of converting the specifications of an electrical circuit into such a layout is called the physical design.
Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of a integrated circuit device. Due to the large number of components and the details required by the fabrication process for very large scale integrated (VLSI) devices, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer-aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn-around time and enhanced chip performance. Several different programming languages have been created for electronic design automation (EDA), including Verilog, VHDL and TDML. A typical EDA system receives one or more high level behavioral descriptions of an IC device, and translates this high level design language description into netlists of various levels of abstraction.
Recent years have seen the emergence of several new academic placement tools, especially in the top-down partitioning and analytical domains. Analytical placers optimally solve a relaxed placement formulation, such as minimizing total quadratic wire length. Quadratic placers generally use various numerical optimization techniques to solve a linear system. Two popular techniques are known as conjugate gradient (CG) and successive over-relaxation (SOR). The PROUD placer uses the SOR technique, while the GORDIAN placer employs the CG algorithm.
VLSI placement has been researched for more than three decades, but the problem remains challenging for multiple reasons. Foremost, the scaling of technology and the corresponding increase in circuit density have allowed only scalable placement techniques a viable option in modern chip designs. Due to this complexity increase in modern chips such as application-specific integrated circuits (ASICs), a more hierarchical design methodology has been adopted in design flow simply to reduce the layout turn-around time. Such complex designs are composed based on the logic or function hierarchy. Each hierarchical module is synthesized, placed and routed individually, then later combined together at the top level to complete the full chip. However, placement based on the logic hierarchy may lead to considerably inferior results.
A preferred methodology is to place the entire design flat (or virtually flat) to derive a good physical hierarchy and use it to guide the subsequent physical synthesis process. Region constraint (RC) placement is derived in such a design layout flow. The region constraint in a placement is an artificial constraint, usually dictated by designers, that a certain set of objects (cells or circuit elements) must be placed in a predefined layout area. The region constraints can be determined by logical partitioning in a hierarchical design methodology, or can be defined from electrical constraints such as voltage or clock domains.
Another trend in EDA is the parallelization of CAD algorithms. With the advent of multi-core (multi-processor) systems, many CAD algorithms have been retooled in parallel fashion to take advantage of these advanced hardware systems. Unfortunately the layout process, particularly placement, is one of the areas w here parallelization efforts have not been successful thus far. One of the key issues in parallelization of an algorithm is load balancing of tasks (also known as scheduling). While general load balancing has been well-researched in the distributed computing area, the problem of parallel processing of regionally-constrained placement remains unsolved. This problem is furthermore growing as ever larger numbers of constraint regions (movebounds) are being defined in state-of-the-art chips with millions of gates, leading to significantly worse runtimes.
In light of the foregoing, it would be desirable to devise an improved method for parallelization of regionally-constrained placement which could more efficiently utilize the hardware resources of multi-core systems to decrease placement turn-around time. It would be further advantageous if the method could achieve such efficient placement without degrading the quality of results, for example, in terms of total wirelength.